package my.suveng.leetcode.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class S144 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = null;
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        Solution solution = new Solution();

        List<Integer> integers = solution.preorderTraversal(root);
        for (Integer integer : integers) {
            System.out.printf("%s,", integer);
        }

    }

    //给定一个二叉树，返回它的 前序 遍历。
//
// 示例:
//
// 输入: [1,null,2,3]
//   1
//    \
//     2
//    /
//   3
//
//输出: [1,2,3]
//
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
// Related Topics 栈 树
// 👍 321 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

    static class Solution {


        public List<Integer> preorderTraversal(TreeNode root) {
            return s2(root);
        }

        /**
         * 解法2 递归
         * @author suwenguang
         */
        private List<Integer> s2(TreeNode root) {
            ArrayList<Integer> result = new ArrayList<>();
            help(root,result);
            return result;
        }

        private void help(TreeNode curr, ArrayList<Integer> result) {
            if (curr==null){
                return;
            }

            result.add(curr.val);
            help(curr.left,result);
            help(curr.right,result);
        }


        /**
         * 解法1 栈迭代
         * @author suwenguang
         */
        private List<Integer> s1(TreeNode root) {
            final Stack<TreeNode> stack = new Stack<>();
            final ArrayList<Integer> result = new ArrayList<>();
            stack.push(root);
            TreeNode curr = null;
            while (curr != null || !stack.isEmpty()) {
                curr = stack.pop();
                if (curr == null) {
                    continue;
                }

                result.add(curr.val);
                stack.push(curr.right);
                stack.push(curr.left);
            }
            return result;
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
